/*
题目: 最大相等频率
给你一个正整数数组 nums，请你帮忙从该数组中找出能满足下面要求的 最长 前缀，并返回该前缀的长度：

    从前缀中 恰好删除一个 元素后，剩下每个数字的出现次数都相同。

如果删除这个元素后没有剩余元素存在，仍可认为每个数字都具有相同的出现次数（也就是 0 次）。

https://leetcode.cn/problems/maximum-equal-frequency
 */
public class MaxEqualFreq {
    public int maxEqualFreq(int[] nums) {
        // Key: 元素 Value: 出现次数
        int[] freq = new int[100001];
        // Key: 出现次数 Value: 出现次数的次数
        int[] count = new int[100001];

        int max = 0; // 记录最大的出现次数
        int src = 0;
        for (int i = 0; i < nums.length; i++) {
            int elem = nums[i];
            freq[elem] ++;
            count[freq[elem]] ++;
            count[freq[elem] - 1] --;
            max = Math.max(max, freq[elem]);

            if (max == 1) {  // 如果最大次数就是 1
                src = Math.max(src, i + 1);
            } else if (max * count[max] == i) {   // 如果是 1, x, x, x...
                src = Math.max(src, i + 1);
            } else if ((max - 1) * count[max - 1] + max == i + 1) {   // 如果是 x, x, x, x, x + 1
                src = Math.max(src, i + 1);
            }
        }
        return src;
    }
}
